package com.markus.code.动态规划;

/**
 * Author:markusZhang
 * Date:Create in 2020/8/16 17:39
 * todo: 最长回文子序列
 */
public class Class04_MaxPalindromeSeq {
    /**
     * 给定一个字符串str，求最长的回文子序列。注意区分子序列和子串的不同。
     */
    public int maxPalindromeSeq(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str1 = s.toCharArray();
        //原字符串的倒置
        char[] str2 = new StringBuilder(s).reverse().toString().toCharArray();
        //声明dp数组，dp[i][j]为两个字符串比较到str1[i],str2[j]的相同子序列的最大长度
        int dp[][] = new int[str1.length][str2.length];
        //dp[i][j]有四种情况
        /**
         * 1、不以 i,j结尾的情况
         *      dp[i][j] = dp[i-1][j-1];
         * 2、以i结尾，不以j-1结尾的情况
         *      dp[i][j] = dp[i][j-1];
         * 3、不以i结尾，以j结尾的情况
         *      dp[i][j] = dp[i-1][j];
         * 4、当两个字符相等的时候，考虑它们两个字符串的前一个字符的情况+1
         *      dp[i][j] = dp[i-1][j-1]+1
         * 取上面四种情况的最大值
         */
        dp[0][0] = str1[0] == str2[0] ? 1 : 0;
        for (int i = 1; i < str1.length; i++) {
            dp[0][i] = str1[i] == str2[0] ? 1 : dp[0][i-1];
        }
        for (int i = 1; i < str2.length; i++) {
            dp[i][0] = str1[0] == str2[i] ? 1 : dp[i-1][0];
        }
        for (int i = 1; i < str2.length; i++) {
            for (int j = 1; j < str1.length; j++) {
                dp[i][j] = Math.max(Math.max(dp[i - 1][j - 1], dp[i][j - 1]),dp[i-1][j]);
                if (str2[i] == str1[j]){
                    dp[i][j] = Math.max(dp[i-1][j-1]+1,dp[i][j]);
                }
            }
        }
        return dp[str1.length-1][str2.length-1];
    }

    public static void main(String[] args) {
        String str = "abac";
        Class04_MaxPalindromeSeq demo = new Class04_MaxPalindromeSeq();
        System.out.println(demo.maxPalindromeSeq(str));
    }
}
